# 超时了
from typing import List

class Solution:
    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        totalSum = sum(nums)
        if totalSum == S:
            zeroCount = len([i for i in nums if i == 0])
            return 2 ** zeroCount
        nlen = len(nums)
        last = nums[nlen - 1]
        if nlen == 1:
            if last == S or last + S == 0:
                return 1
            else:
                return 0
        else:
            return self.findTargetSumWays(nums[:-1], S + last) + self.findTargetSumWays(nums[:-1], S - last)


solu = Solution()
print(solu.findTargetSumWays([1, 1, 1, 1, 1], 3))
print(solu.findTargetSumWays([1, 0], 1))
